package dfs;

import java.util.ArrayList;
import java.util.List;

/**
 * 给定两个整数 n 和 k，返回 1 ... n 中所有可能的 k 个数的组合。
 * https://leetcode-cn.com/problems/combinations/
 *
 * @author: luo
 * @email: luo@nyist.edu.cn
 * @date: 2021/1/25 12:07
 */
public class Combine {
    public static void main(String[] args) {

        System.out.println(combine(4, 2));
    }

    public static List<List<Integer>> combine(int n, int k) {

        List<List<Integer>> list = new ArrayList<>();
        backtracking(0, k, new ArrayList<>(), new boolean[n + 1], list);
        return list;
    }

    private static void backtracking(int t, int k, List<Integer> nums, boolean[] strack, List<List<Integer>> list) {
        if (t >= k) {
            list.add(new ArrayList<>(nums));
        } else {
            for (int i = 1; i < strack.length; i++) {
                if (t != 0 && nums.get(t - 1) > i) continue;
                if (!strack[i]) {
                    nums.add(i);
                    strack[i] = true;
                    backtracking(t + 1, k, nums, strack, list);
                    nums.remove(t);
                    strack[i] = false;
                }
            }
        }
    }
}
